Örnek : Büyük O notasyonu hesabı

Bir algoritmanın yürütme zamanı bağıntısı T(n)= An²+Bn+C şeklinde hesaplanmıştır. Burada A, B ve C sabit sayılar olup n ise eleman sayısını göstermektedir. Bu algoritmanın büyük o notasyonuna göre karmaşıklığı ne olur?

Çözüm: Büyük o notasyonunu bulmak için birçok yol vardır. En kolay görüneni aşağıdaki gibi olabilir. Bağıntımız T(n)= An²+Bn+C şeklindedir. Sağ taraf n²'ye bölünürse,

aşağıdaki gibi bir sonuç elde edilir.

Burada 'a giderken birinci terim sabit, ikinci ve üçüncü terimler sıfıra doğru yaklaşır. Dolayısıyla için A sabiti kalır. Dolayısıyla T(n)= An²+Bn+C bağıntısı için büyük o notasyonundaki karmaşıklık için O(n²) denilebilir. Bu karmaşıklık belirli bir A değeri ve üstü için geçerlidir.

Örneğin ise T(n)= 3n²+7n+5, eşitliği sağ tarafı n²'ye bölünürse,

elde edilir. Burada A değeri 3'tür.